package com.hh.demo;
import java.awt.BorderLayout;
import java.awt.FlowLayout;
import java.awt.Font;

import javax.swing.*;

public class Symtriangle {

    static int n;//第一行的符号个数
    static int half;//n*(n+1)/4 即当前符号总数量的一半
    static int count;//当前“+”或者“-”的个数
    static int[][] p;//符号三角形矩阵
    static long sum;//已找到的符号三角形的个数
    static String str="";
    public static float Compute(int t) {
        n=t;
        count=0;
        sum=0;
        half=n*(n+1)/2;
        if(half%2==1) {
            return 0;
        }
        half=half/2;
        p=new int[n+1][n+1];
        backtrack(1);
        JFrame jf=new JFrame();
        jf.setLayout(new FlowLayout());
        JPanel jp=new JPanel();
        jp.setLayout(new BorderLayout());
        JTextArea jta=new JTextArea(str,20,20);
        jta.setFont(new Font("宋体", Font.PLAIN, 20));
        jp.add(jta);
        jf.add(jp);
        jf.setTitle("符号三角形打印图");
        jf.setLocation(400, 250);
        jf.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
        jf.setVisible(true);
        jf.setSize(240,550);
        return sum;
    }


    public static void backtrack(int m) {

        if((count>half)||(m*(m-1)/2-count>half)) //减去不符合条件的子树
            return;
        if(m>n)
        {
            sum++;
            //打印符号三角形
            for(int i=1;i<=n;i++)
            {
                for(int k=1;k<i;k++)
                {
                    System.out.print(" ");
                    str+=" ";

                }
                for(int j=1;j<=n;j++)
                {
                    if(p[i][j]==0&&j<=n-i+1) {
                        System.out.print("+" + " ");
                        str+="+ ";

                    }
                    else if(p[i][j]==1&&j<=n-i+1) {
                        System.out.print("-" + " ");
                        str+="- ";

                    }
                    else {
                        System.out.print("  ");
                        str+="  ";

                    }
                }
                System.out.println();
                str+="\n";

            }
            System.out.println();
            str+="\n";
        }
        else
        {
            //每个位置都有两种情况0,1
            for(int i=0;i<2;i++)
            {
                p[1][m]=i;
                count+=i;//计算“-”的个数

                //接下来绘制其余的n-1行
                for(int j=2;j<=m;j++)
                {
                    //通过异或的方式求其余行数的放置方式
                    p[j][m-j+1]=p[j-1][m-j+1]^p[j-1][m-j+2];
                    count+=p[j][m-j+1];

                }
                backtrack(m+1);

                for(int j=2;j<=m;j++)
                {
                    count-=p[j][m-j+1];
                }
                count-=i;

            }
        }

    }
    public Symtriangle(){

        String title="符号三角形算法输出";
        System.out.println("问题三：5-4符号三角形问题");
        String s=JOptionPane.showInputDialog("请输入第一行符号个数x(x>2)");
        JOptionPane.showMessageDialog(null,"输入成功，三角形打印中...");
        int x=Integer.parseInt(s);
        float SUM=Compute(x);
        System.out.print("符号三角形总数："+SUM);
        JOptionPane.showMessageDialog(null,"符号三角形总数："+SUM,title,JOptionPane.INFORMATION_MESSAGE);
    }
}
